#include "minheap.h"



mW_minheap * mW_minheap_create (void * comparison_function)
{

	mW_minheap * minheap;
	
	minheap = (mW_minheap *) malloc(sizeof(mW_minheap));
	if (minheap == NULL)
		mW_error("Failed to allocate memory for minheap");

	minheap->size = 0;
	minheap->comparison_function = comparison_function;
	minheap->top = NULL;
	
	return minheap;
	
}



mW_minheap_item * mW_minheap_create_item (void * data)
{
	
	mW_minheap_item * minheap_item;
	
	minheap_item = (mW_minheap_item *) malloc(sizeof(mW_minheap_item));
	if (minheap_item == NULL)
		mW_error("Failed to allocate memory for minheap_item");
	
	minheap_item->data = data;
	minheap_item->left = NULL;
	minheap_item->right = NULL;
	minheap_item->parent = NULL;
	
	return minheap_item;
	
}



int mW_minheap_delete_top (mW_minheap * minheap)
{
	
	mW_minheap_item * current_item;
	int position;
	
	
	if (minheap->size == 1)
	{
		mW_minheap_destroy_item(minheap->top);
		minheap->top = NULL;
		minheap->size = 0;
		return 1;
	}
	
	
	current_item = minheap->top;
	
	position = minheap->size - 1;

	while (1)
	{
		if (position % 2 == 0)
		{
			if (current_item->left == NULL)
				break;
			else
				current_item = current_item->left;
		}
		else
		{
			if (current_item->right == NULL)
				break;
			else
				current_item = current_item->right;
		}
		position /= 2;
	}
	
	free(minheap->top->data);
	minheap->top->data = current_item->data;
	if (current_item->parent->left == current_item)
		current_item->parent->left = NULL;
	else
		current_item->parent->right = NULL;
	free(current_item);
	
	minheap->size--;


	mW_minheap_downheap(minheap, minheap->top);
	
	return 1;
	
}



int mW_minheap_destroy (mW_minheap * minheap)
{
	
	mW_minheap_destroy_item(minheap->top);
	
	free(minheap);
	
	return 1;	
	
}



int mW_minheap_destroy_item (mW_minheap_item * minheap_item)
{
	
	if (minheap_item == NULL)
		return 0;
	else
	{
		if (minheap_item->left != NULL)
			mW_minheap_destroy_item(minheap_item->left);
		if (minheap_item->right != NULL)
			mW_minheap_destroy_item(minheap_item->right);
	}
	
	free(minheap_item->data);
	free(minheap_item);
	
	return 1;

}



int mW_minheap_downheap (mW_minheap * minheap, mW_minheap_item * minheap_item)
{
	
	void * tmp_data;
	mW_minheap_item * smaller_child;

	// if both children exist
	if ((minheap_item->left != NULL) && (minheap_item->right != NULL))
	{
		
		// select the smaller of the two children
		if (minheap->comparison_function(minheap_item->left->data, minheap_item->right->data) <= 0)
			smaller_child = minheap_item->left;
		else
			smaller_child = minheap_item->right;
		
		// swap the data between this child and the smaller child
		tmp_data = smaller_child->data;
		smaller_child->data = minheap_item->data;
		minheap_item->data = tmp_data;
		
		// downheap the smaller child
		mW_minheap_downheap(minheap, smaller_child);
		
	}
	else if (minheap_item->left != NULL)
	{
		
		if (minheap->comparison_function(minheap_item->left->data, minheap_item->data) < 0)
		{
			tmp_data = minheap_item->left->data;
			minheap_item->left->data = minheap_item->data;
			minheap_item->data = tmp_data;
			
			mW_minheap_downheap(minheap, minheap_item->left);
		}
		
	}
	else if (minheap_item->right != NULL)
	{
		
		if (minheap->comparison_function(minheap_item->right->data, minheap_item->data) < 0)
		{
			tmp_data = minheap_item->right->data;
			minheap_item->right->data = minheap_item->data;
			minheap_item->data = tmp_data;
			
			mW_minheap_downheap(minheap, minheap_item->right);
		}
	}
	
	return 1;
	
}



int mW_minheap_get_size (mW_minheap * minheap)
{
	
	return minheap->size;
	
}



void * mW_minheap_get_top (mW_minheap * minheap)
{
	
	return minheap->top->data;
	
}



int mW_minheap_insert (mW_minheap * minheap, void * data)
{
	
	int position = minheap->size;
	mW_minheap_item * new_item;
	mW_minheap_item * current_item;
	
	new_item = mW_minheap_create_item(data);
	
	if (minheap->size == 0)
	{	
		minheap->top = new_item;
		minheap->size++;
		return 1;
	}
	
	current_item = minheap->top;
	
	position = minheap->size;

	while (1)
	{
		if (position % 2 == 0)
		{
			if (current_item->left == NULL)
				break;
			else
				current_item = current_item->left;
		}
		else
		{
			if (current_item->right == NULL)
				break;
			else
				current_item = current_item->right;
		}
		position /= 2;
	}
	

	if (position % 2 == 0)
		current_item->left = new_item;
	else
		current_item->right = new_item;
		
	minheap->size++;
		
	
	new_item->parent = current_item;
	
	
	mW_minheap_upheap(minheap, new_item);
	
	return 1;
	
}
		
		
		
int mW_minheap_upheap (mW_minheap * minheap, mW_minheap_item * minheap_item)
{
	
	void * tmp_data;
	
	if (minheap_item->parent == NULL)
		return 1;
	if (minheap->comparison_function(minheap_item->data, minheap_item->parent->data) < 0)
	{
		
		// swap data
		tmp_data = minheap_item->data;
		minheap_item->data = minheap_item->parent->data;
		minheap_item->parent->data = tmp_data;
		
		mW_minheap_upheap(minheap, minheap_item->parent);
		
	}
	
	return 1;
	
}



void * mW_minheap_search (mW_minheap * minheap, void * data, int (* search_function) (void *, void *))
{	
	
	if (minheap->top == NULL)
		return NULL;
	
	return mW_minheap_search_item(minheap->top, data, search_function);
	
}



void * mW_minheap_search_item (mW_minheap_item * minheap_item, void * data, int (* search_function) (void *, void *))
{
	
	void * search_result;
	
	if (minheap_item->data == NULL)
		return NULL;
	
	if (search_function(minheap_item->data, data) == 0)
		return minheap_item->data;
		
	if (minheap_item->left != NULL)
	{
		search_result = mW_minheap_search_item (minheap_item->left, data, search_function);
		if (search_result != NULL)
			return search_result;
	}
	
	if (minheap_item->right != NULL)
	{
		search_result = mW_minheap_search_item (minheap_item->right, data, search_function);
		if (search_result != NULL)
			return search_result;
	}
		
	return NULL;
	
}



mW_minheap_item * mW_minheap_get_node (mW_minheap * minheap, int position, int depth)
{
	
	int i;
	mW_minheap_item * node;
	
	
	if (minheap->size == 0)
		return NULL;
	else if (minheap->size == 1)
		return minheap->top;
	else
		node = minheap->top;
	
	
	for (i = 0; i < depth; i++)
	{
		
		if (position % 2 == 0)
			node = node->left;
		else
			node = node->right;
		position /= 2;
		
	}
	
	return node;
	
}
